// https://leetcode.cn/problems/unique-binary-search-trees/

#include <iostream>

using namespace std;

// 核心思想：排列组合各种节点为根节点的情况，数量为左子树数量*右子树数量。累加就是该值
class Solution {
public:
    int numTrees(int n) {
        int dp[20];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            int tmp = 0;
            for (int j = 0; j < i; j++) {
                tmp += dp[j] * dp[i - 1 - j];
            }
            dp[i] = tmp;
        }
        return dp[n];
    }


};

int main() {
    Solution so;
    int n = 4;
    int sum = so.numTrees(n);
    cout << sum << endl;
    return 0;
}